package 代码记录.指定公司代码练习记录.华为_2024.分值100.第36start;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

/**
 * @author zx
 * @create 2024-02-16 13:18
 * 看懂人家的代码了
 */
public class 堆内存申请_75 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 读取输入
        int n = Integer.parseInt(sc.nextLine());
        List<HeapMemory> allocatedMemory = new ArrayList<>();
        while (sc.hasNextLine()) {
            String[] input = sc.nextLine().split(" ");
            if (input.length != 2) {
                break; // 如果输入不符合要求，跳出循环
            }
            int offset = Integer.parseInt(input[0]);
            int size = Integer.parseInt(input[1]);
            allocatedMemory.add(new HeapMemory(offset, size));
        }
        // 执行内存分配
        int res = allocateMemory(n, allocatedMemory);
        System.out.println(res);
        sc.close(); //关闭Scanner对象(没有这行代码不会输出程序结果)
    }

    public static int allocateMemory(int n, List<HeapMemory> memory) {
        Collections.sort(memory);  //按偏移地址排序
        for (int i = 0; i < memory.size() - 1; i++) {
            //对每个相邻的内存块进行比较，计算两个内存块之间的空闲空间
            //如果存在足够大的空闲内存块，返回该空闲空间的起始偏移地址。
            int startOffset = memory.get(i).getOffset() + memory.get(i).getSize();
            int endOffset = memory.get(i + 1).getOffset();
            if (endOffset - startOffset >= n) {
                return startOffset;
            }
        }
        // 检查最后一个分配内存块之后的空闲空间是否足够
        int last = memory.get(memory.size() - 1).getOffset() + memory.get(memory.size() - 1).getSize();
        if (100 - last >= n) {
            return last;
        }
        return -1;//无法找到足够的空间
    }

    static class HeapMemory implements Comparable<HeapMemory> {
        private final int offset;
        private final int size;

        public HeapMemory(int offset, int size) {
            this.offset = offset;
            this.size = size;
        }

        public int getOffset() {
            return offset;
        }

        public int getSize() {
            return size;
        }

        @Override
        public int compareTo(HeapMemory other) {
            return Integer.compare(this.offset, other.offset);
        }
    }
}
